# -*- coding: utf-8 -*-

'''
projecto- classe destinada ao algoritmo de ordenação: insertion sort
autor- Ana Isabel Marques 6052
data de criação do módulo- 27/05/2013

Complexidade Computacional:
        pior caso - O(n²)
        caso médio - O(n²)
        melhor caso - O(n)    
'''

class InsertionSort:
        '''
        Constructor
        @param A - lista de números inteiros
        '''
        def __init__(self, A):
                self.A = A
                pass

        '''
        Ordena uma lista através do algoritmo de ordenação: insertion sort
	'''
        def insertion_sort(self):
                for j in xrange (1, len(self.A)):
                        key = self.A[j]
                        i = j - 1

                        while i > -1 and self.A[i] > key:

                                self.A[i+1] = self.A[i]
                                i = i - 1
                                pass

                        self.A[i+1] = key
                        pass

                return self.A
        pass
pass

